Библиотека собеса по Data Science | вопросы с собеседований

🐍Решение задачи на Python «сумма двух» (Two sum)

Вам даны массив и число N. Нужно вернуть True, если в массиве есть такие два числа A и B, что их сумма A + B даёт N. В противном случае нужно вернуть False.
Примеры:
[1, 2, 3, 4], 5 ⇒ True
[3, 4, 6], 6 ⇒ False


✔️Можно, конечно, применить брутфорс, но есть решение получше. Его сложность составит O(n). Вот как оно выглядит:

def two_sum(numbers, target):
    index = {num: i for (i, num) in enumerate(numbers)}

    n = len(numbers)

    for i in range(n):
        a = numbers[i]
        b = target - a

        if b in index:
            j = index[b]
            if i != j:
                return True

    return False

Здесь сначала создаётся словарь index, который хранит числа из массива в качестве ключей и их индексы в массиве в качестве значений. Затем идёт перебор элементов массива. Для каждого элемента a вычисляется число b, которое необходимо для достижения суммы target. Далее проверяется, содержится ли b в словаре index. Если да, то дополнительно проверяется, не совпадает ли индекс текущего элемента a с индексом элемента b. Если индексы различны, это означает, что была найдена пара чисел, сумма которых равна target.

#алгоритмы
#python

Please open Telegram to view this post

VIEW IN TELEGRAM

www.tg-me.com/ms/Библиотека собеса по Data Science | вопросы с собеседований/com.ds_interview_lib/192

1.6K viewsJan 17, 2024 at 12:03

🐍Решение задачи на Python «сумма двух» (Two sum)

Вам даны массив и число N. Нужно вернуть True, если в массиве есть такие два числа A и B, что их сумма A + B даёт N. В противном случае нужно вернуть False.
Примеры:
[1, 2, 3, 4], 5 ⇒ True
[3, 4, 6], 6 ⇒ False


✔️Можно, конечно, применить брутфорс, но есть решение получше. Его сложность составит O(n). Вот как оно выглядит:

def two_sum(numbers, target):
    index = {num: i for (i, num) in enumerate(numbers)}

    n = len(numbers)

    for i in range(n):
        a = numbers[i]
        b = target - a

        if b in index:
            j = index[b]
            if i != j:
                return True

    return False